<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        // 
        function LinkedList(){
            // 节点，有当前节点数据的属性和指向下一个节点的属性,默认是最后一个节点，所以next为null
            function Node(data){
                this.data = data
                this.next = null
            }
            // 保存链表个数
            this.length = 0
            // 链表头，默认指向是null
            this.head = null

            // 向链表中尾部插入一个节点
            LinkedList.prototype.append = function ( data){
                // 1、创建一个节点
                let node = new Node(data)
                // 2、判断是否是链表中第一个节点
                if ( this.length == 0){
                    // 2.1 将链表头指向第一个节点
                    this.head = node
                }else{
                    // 2.2 从第一个节点开始找,如果current.next存在，则重新将该节点赋值给current，直到.next为null
                    let current = this.head
                    while( current.next ){
                        current = current.next
                    }
                    // 3 找到最后一个节点了,将其next指向最后一个节点
                    current.next = node
                }
                // 4 链表数加1
                this.length += 1
            }
      
            // 2 toString 
            LinkedList.prototype.toString = function (){
                // 获取头部指向
                let current = this.head
                // 保存结果
                let resultStr = ''
                while(current){
                    console.log(current)
                    resultStr += current.data + ' '
                    // 将下一个指向的指针赋值
                    current = current.next
                }
                return resultStr
            }
            
            // 3、插入方法:参数一为插入的下标，
            LinkedList.prototype.insert = function(position,data){

                // 越界处理
                if ( position < 0 || this.length < position ) return false

                // 创建节点
                let node = new Node(data)
                // 1从头插入
                if ( position === 0 ){
                    // 将新插入的节点的指向同链表头指向一致的节点
                    node.next = this.head
                    // 将链表头指向新插入的节点
                    this.head = node
                }else{
                    // 2中间或末尾插入
                    let index = 0
                    // 标识插入的位置
                    let current = this.head
                    // 标识插入位置的前面节点
                    let previous = null
                    
                    // 通过下标循环，previous标识插入之前的节点，让其next指向插入的节点。 current标识插入之后的节点,让current指向插入新节点后边的节点
                    while( index++ < position ){
                        // 让插入的新节点(A)之前的节点的指向A
                        previous = current
                        // 让A指向下插入后 后面的节点
                        current = current.next
                    }
                    // 让插入前的节点指向插入节点
                    previous.next = node
                    // 让插入的节点指向插入后边的节点
                    node.next = current

                    // 节点数+1，并返回成功 
                    this.length += 1
                    return true
                }
            }
            
            // 4、查询get方法
            LinkedList.prototype.get = function(position) {
                // 判断越界
                if( position >= this.length || position < 0) return null

                let current = this.head
                let index = 0 
                /**
                 *position = 2
                 *index = 0 ,current = 链表[1]
                 *index = 1 ,current = 链表[2]
                 *index = 2 ,进不去循环
                 * 
                 */
                while( index < position ){
                    current = current.next
                    index++
                }
                // 将对应的节点的数据返回
                return current.data
            }
        
            // 5、indexOf方法
            LinkedList.prototype.indexOf = function(data) {
                // 判断越界
                let current = this.head
                let index = 0
                while( index < this.length) {
                    if ( current.data == data){
                        return index
                    }
                    current = current.next
                    index++
                }
                // 到这里表示没有找到
                return -1
            }

            // 6、update方法
            LinkedList.prototype.update = function(position,data) {
                // 判断越界
                if( position >= this.length || position < 0) return false

                let current = this.head
                let index = 0
                // 通过循环，将current指向要更新的节点
                while( index < position ) {
                    current = current.next
                    index++
                }
                // 更新节点
                current.data = data
                return true
            }
            
            // 7、removeAt从列表中移出特定的一位
            LinkedList.prototype.removeAt = function(position) {
                // 判断越界
                if( position >= this.length || position < 0) return null

                let current = this.head 
                // 删除的是第一个
                if ( position === 0 ){
                    // 将链表头指向链表的next指向
                    this.head = this.head.next
                }else{
                    // 表示当前节点的前一个，默认以第一个节点开始，所以为null
                    let previous = null
                    let index = 0 
                    while ( index < position ){
                        previous = current
                        current = current.next
                        index++ 
                    }
                    // 将当前节点B(其next指向C节点)的前一个节点A(其next指向B节点)的next指向C
                    previous.next = current.next
                }

                this.length -= 1
                return current.data
            }
            
            // 8 remove
            LinkedList.prototype.remove = function (data) {
                // 获取索引
                let position = this.indexOf(data)
                return this.removeAt(position)
            }
        }

        const list = new LinkedList()
        list.append('aaa')
        list.append('bbb')
        list.append('ccc')
        // alert(list)
        console.log(list.insert(3,'111'))
        // alert(list.toString())
        // alert(list.get(0))
        // alert(list.indexOf('aaaa'))
        // alert(list.update(0,'---00'))
        // alert(list.update(3,'---02222343330'))
        alert(list)
        // alert(list.removeAt(0))
        alert(list)
        console.log(list.remove('aaa'))

    </script>
</body>
</html>